<!DOCTYPE html>
<html>
<head><meta name="generator" content="Hexo 3.9.0">
  <meta charset="utf-8">
  

  
  <title>LeetCode--移位符 | Hexo</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
  <meta name="description" content="不得不说，自己的算法是真的差，差的也不仅仅是算法，更多的还是自己上课期间忽略的基础知识。LeetCode第29题，题目描述如下：  给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。返回被除数 dividend 除以除数 divisor 得到的商。   示例 1:输入: dividend = 10, divisor = 3输出: 3">
<meta name="keywords" content="TheKnowledgeOf">
<meta property="og:type" content="article">
<meta property="og:title" content="LeetCode--移位符">
<meta property="og:url" content="http://yoursite.com/2019/03/28/LeetCode-移位符/index.html">
<meta property="og:site_name" content="Hexo">
<meta property="og:description" content="不得不说，自己的算法是真的差，差的也不仅仅是算法，更多的还是自己上课期间忽略的基础知识。LeetCode第29题，题目描述如下：  给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。返回被除数 dividend 除以除数 divisor 得到的商。   示例 1:输入: dividend = 10, divisor = 3输出: 3">
<meta property="og:locale" content="default">
<meta property="og:updated_time" content="2019-06-24T00:05:42.601Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="LeetCode--移位符">
<meta name="twitter:description" content="不得不说，自己的算法是真的差，差的也不仅仅是算法，更多的还是自己上课期间忽略的基础知识。LeetCode第29题，题目描述如下：  给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。返回被除数 dividend 除以除数 divisor 得到的商。   示例 1:输入: dividend = 10, divisor = 3输出: 3">
  
    <link rel="alternate" href="/atom.xml" title="Hexo" type="application/atom+xml">
  
  
    <link rel="icon" href="/favicon.png">
  
  
    <link href="//fonts.googleapis.com/css?family=Source+Code+Pro" rel="stylesheet" type="text/css">
  
  <link rel="stylesheet" href="/css/style.css">
</head>
</html>
<body>
  <div id="container">
    <div id="wrap">
      <header id="header">
  <div id="banner"></div>
  <div id="header-outer" class="outer">
    <div id="header-title" class="inner">
      <h1 id="logo-wrap">
        <a href="/" id="logo">Hexo</a>
      </h1>
      
    </div>
    <div id="header-inner" class="inner">
      <nav id="main-nav">
        <a id="main-nav-toggle" class="nav-icon"></a>
        
          <a class="main-nav-link" href="/">Home</a>
        
          <a class="main-nav-link" href="/archives">Archives</a>
        
      </nav>
      <nav id="sub-nav">
        
          <a id="nav-rss-link" class="nav-icon" href="/atom.xml" title="RSS Feed"></a>
        
        <a id="nav-search-btn" class="nav-icon" title="Search"></a>
      </nav>
      <div id="search-form-wrap">
        <form action="//google.com/search" method="get" accept-charset="UTF-8" class="search-form"><input type="search" name="q" class="search-form-input" placeholder="Search"><button type="submit" class="search-form-submit">&#xF002;</button><input type="hidden" name="sitesearch" value="http://yoursite.com"></form>
      </div>
    </div>
  </div>
</header>
      <div class="outer">
        <section id="main"><article id="post-LeetCode-移位符" class="article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/2019/03/28/LeetCode-移位符/" class="article-date">
  <time datetime="2019-03-28T06:15:37.000Z" itemprop="datePublished">2019-03-28</time>
</a>
    
  <div class="article-category">
    <a class="article-category-link" href="/categories/TheKnowledgeOf/">TheKnowledgeOf</a>
  </div>

  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 class="article-title" itemprop="name">
      LeetCode--移位符
    </h1>
  

      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <p>不得不说，自己的算法是真的差，差的也不仅仅是算法，更多的还是自己上课期间忽略的基础知识。<br>LeetCode第29题，题目描述如下：</p>
<blockquote>
<p>给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。<br>返回被除数 dividend 除以除数 divisor 得到的商。</p>
</blockquote>
<blockquote>
<p>示例 1:<br>输入: dividend = 10, divisor = 3<br>输出: 3<br>示例 2:<br>输入: dividend = 7, divisor = -3<br>输出: -2</p>
</blockquote>
<blockquote>
<p>说明:<br>被除数和除数均为 32 位有符号整数。<br>除数不为 0。<br>假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231,  231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。</p>
</blockquote>
<p>看到这道题，我的第一个想法：“一个数除以另一个数，可以转化成多次减法运算”。<br>然后我的第一个骚操作来了：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">soultion</span></span>&#123;</span><br><span class="line">	<span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">divide</span><span class="params">(<span class="keyword">int</span> dividend, <span class="keyword">int</span> divisor)</span> </span>&#123;</span><br><span class="line">		<span class="keyword">int</span> result = <span class="number">0</span>;</span><br><span class="line">		<span class="keyword">while</span>(dividend &gt;= divisor)&#123;</span><br><span class="line">			dividend = dividend - divisor;</span><br><span class="line">			result++;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">return</span> result;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>现在看到这段代码，我自己都佩服我自己。（手动鼓掌）</p>
<h3 id="其实这个想法还是没错的，错在于没考虑极端情况"><a href="#其实这个想法还是没错的，错在于没考虑极端情况" class="headerlink" title="其实这个想法还是没错的，错在于没考虑极端情况"></a>其实这个想法还是没错的，错在于没考虑极端情况</h3><p>举例子说明，比如第一组测试样例，10除以3这种“正常数字”（日常接触得到的计算量级）来说，这段代码并没有问题，可以正常运行，花费的时间也在可以接受的范围之内，但是现在问题来了：极端情况下会怎么样呢？</p>
<p>我们给dividend取int的最大值（2的31次方-1），divisor取值1，执行这段代码需要耗时多久？<br>不难算出，while循环需要执行2的31次方-1次，也就是二十一亿多次，很明显时间上是不允许的。所以我们需要改进这个算法。</p>
<p>在百度的帮助下，我认识了一个符号，叫移位符。好吧，这可能真的是很基础的东西，但是原谅我的菜，我真的是第一次听说这个东西。<br>简单介绍下移位符的作用：</p>
<blockquote>
<p>移位运算符在程序设计中，是位操作运算符的一种。移位运算符可以在二进制的基础上对数字进行平移。按照平移的方向和填充数字的规则分为三种：&lt;&lt;(左移)、&gt;&gt;(带符号右移)和&gt;&gt;&gt;(无符号右移)。</p>
</blockquote>
<p>拿右移<code>&gt;&gt;</code>举例子， <code>7&gt;&gt;1</code> 相当于 <code>7/2</code> <code>7&gt;&gt;2</code>相当于 <code>7/4</code>，即右移n位相当于除以2的n次方。<br>（从结果上看是这种效果）</p>
<p>具体的运算例子 <code>11&gt;&gt;2</code></p>
<blockquote>
<p>11的二进制形式为：0000 0000 0000 0000 0000 0000 0000 1011，然后把低位的最后两个数字移出，因为该数字是正数，所以在高位补零。则得到的最终结果是0000 0000 0000 0000 0000 0000 0000 0010。转换为十进制是2。</p>
</blockquote>
<p>有了这个积累，我们再来看这道题。<br>我们现在需要做的事情，就是减少while循环的次数，怎么减少呢？当然就是每次循环多减一点啦！<br>先上代码：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">divide</span><span class="params">(<span class="keyword">int</span> dividend, <span class="keyword">int</span> divisor)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">long</span> m,n;</span><br><span class="line">        m = Math.abs((<span class="keyword">long</span>)dividend);<span class="comment">//被除数的绝对值</span></span><br><span class="line">        n = Math.abs((<span class="keyword">long</span>)divisor);<span class="comment">//除数的绝对值</span></span><br><span class="line">        <span class="keyword">if</span>(n == <span class="number">0</span> || (dividend == Integer.MIN_VALUE &amp;&amp; divisor == -<span class="number">1</span>))</span><br><span class="line">           <span class="keyword">return</span> Integer.MAX_VALUE;</span><br><span class="line">           <span class="keyword">int</span> sign = ((dividend &lt; <span class="number">0</span>) ^ (divisor &lt; <span class="number">0</span>)) ? -<span class="number">1</span> : <span class="number">1</span>;</span><br><span class="line">         <span class="keyword">if</span>(n == <span class="number">1</span>) <span class="keyword">return</span> (<span class="keyword">int</span>)((sign&gt;<span class="number">0</span>)? m:-m);</span><br><span class="line">           <span class="keyword">long</span> result = <span class="number">0</span>;</span><br><span class="line">           <span class="keyword">while</span>(m&gt;= n)&#123;</span><br><span class="line">                <span class="keyword">long</span> temp = n;</span><br><span class="line">                <span class="keyword">long</span> count = <span class="number">1</span>;</span><br><span class="line">               <span class="keyword">while</span>(m &gt; (temp&lt;&lt;<span class="number">1</span>))&#123;</span><br><span class="line">                   temp = temp&lt;&lt;<span class="number">1</span>;</span><br><span class="line">                   count = count&lt;&lt;<span class="number">1</span>;</span><br><span class="line">               &#125;</span><br><span class="line">               result = result + count;</span><br><span class="line">               m = m - temp;</span><br><span class="line">           &#125;</span><br><span class="line">           <span class="keyword">return</span> (<span class="keyword">int</span>)((sign&gt;<span class="number">0</span>)? result:-result);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>好了，现在我来解释下这个程序。</p>
<p>首先看内层循环 <code>while(m &gt; (temp&lt;&lt;1))</code>里面的东西，<code>temp</code>等于除数，当m（被除数的绝对值）大于两倍的除数的时候，temp乘以二，count乘以二，循环到temp的两倍大于被除数m为止。这样循环的结果是循环次数会以指数级减少。<br>我们还是拿最开始的例子，dividend = pow（2，31）-1；divisor = 1；<br>第一次进入外层循环，然后进入内层循环，内层的while执行30次后结束，此时temp = 2的30次方，count = 2的30次方。接着向下执行第18和第19两行代码，整个循环第一次结束后，m = 1。</p>
<h3 id="对比21亿次循环，我们的算法有了质的飞跃（为自己鼓掌）。"><a href="#对比21亿次循环，我们的算法有了质的飞跃（为自己鼓掌）。" class="headerlink" title="对比21亿次循环，我们的算法有了质的飞跃（为自己鼓掌）。"></a>对比21亿次循环，我们的算法有了质的飞跃（为自己鼓掌）。</h3><h3 id="但是，我的骚操作远没有结束上面放出的这段代码是我最后一次提交成功的代码。"><a href="#但是，我的骚操作远没有结束上面放出的这段代码是我最后一次提交成功的代码。" class="headerlink" title="但是，我的骚操作远没有结束上面放出的这段代码是我最后一次提交成功的代码。"></a>但是，我的骚操作远没有结束上面放出的这段代码是我最后一次提交成功的代码。</h3><p>前面还有十几次失败经验还没总结呢。</p>
<p>首先第一个问题，变量声明里面的 <code>long</code> 为什么要用long？<br>还是上面那个极端的例子，在判断的时候 temp&lt;&lt;1，如果用int，会发生超出int最大值的问题，然后temp会变成一个负数，然后这个循环永远结束不了，然后就超时了。。。。。。</p>
<p>第二个是边界值问题，在这个题目中，边界情况下只有一种可能会越界，就是当被除数为int最小值，除数为-1时，得到的商会大于int的最大值，所以我们需要考虑这种情况。</p>
<p>最后就是符号判别问题，用异或判断被除数与除数是否相同，保证输出结果符号的正确性。（当然不想用异或运算的也可以使用if写明条件判断）</p>
<p>当然按照这个思路做完以后，我也有个问题：为什么非要用移位运算符呢？<br>count = count + count不也一样么？<br>抱着这个疑问，我又改了改程序，又跑了一次。</p>
<h2 id="结论是：确实可以，只不过会比移位运算符慢2ms"><a href="#结论是：确实可以，只不过会比移位运算符慢2ms" class="headerlink" title="结论是：确实可以，只不过会比移位运算符慢2ms"></a>结论是：确实可以，只不过会比移位运算符慢2ms</h2><p>至于为什么会慢2ms…我给自己留个坑吧，初步猜测是计算机处理二进制会更快一些，当然这只是猜测而已，具体什么原因我有空再去验证一下……</p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://yoursite.com/2019/03/28/LeetCode-移位符/" data-id="ck4r400rf007il0w0mnmx5cyp" class="article-share-link">Share</a>
      
      
  <ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/TheKnowledgeOf/">TheKnowledgeOf</a></li></ul>

    </footer>
  </div>
  
    
<nav id="article-nav">
  
    <a href="/2019/04/07/JS编写位置/" id="article-nav-newer" class="article-nav-link-wrap">
      <strong class="article-nav-caption">Newer</strong>
      <div class="article-nav-title">
        
          JS编写位置
        
      </div>
    </a>
  
  
    <a href="/2019/03/22/Git推送到项目笔记/" id="article-nav-older" class="article-nav-link-wrap">
      <strong class="article-nav-caption">Older</strong>
      <div class="article-nav-title">Git推送到项目笔记</div>
    </a>
  
</nav>

  
</article>

</section>
        
          <aside id="sidebar">
  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Categories</h3>
    <div class="widget">
      <ul class="category-list"><li class="category-list-item"><a class="category-list-link" href="/categories/Ajax/">Ajax</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/CSS/">CSS</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/CSS3/">CSS3</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/Dart/">Dart</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/Flutter/">Flutter</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/Git/">Git</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/HTML/">HTML</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/HTML5/">HTML5</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/JSON/">JSON</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/Java/">Java</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/JavaScript/">JavaScript</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/QT/">QT</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/React/">React</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/Sass/">Sass</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/TheKnowledgeOf/">TheKnowledgeOf</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/TypeScript/">TypeScript</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/bootstrap/">bootstrap</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/jQuery/">jQuery</a></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Tags</h3>
    <div class="widget">
      <ul class="tag-list"><li class="tag-list-item"><a class="tag-list-link" href="/tags/Ajax/">Ajax</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/CSS/">CSS</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/CSS3/">CSS3</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Dart/">Dart</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Flutter/">Flutter</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Git/">Git</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/HTML/">HTML</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/HTML5/">HTML5</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/JSON/">JSON</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Java/">Java</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/JavaScript/">JavaScript</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Javascript/">Javascript</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/QT/">QT</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/React/">React</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Sass/">Sass</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/TheKnowledgeOf/">TheKnowledgeOf</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/TypeScript/">TypeScript</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/bootstrap/">bootstrap</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/jQuery/">jQuery</a></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Tag Cloud</h3>
    <div class="widget tagcloud">
      <a href="/tags/Ajax/" style="font-size: 12.22px;">Ajax</a> <a href="/tags/CSS/" style="font-size: 18.89px;">CSS</a> <a href="/tags/CSS3/" style="font-size: 17.78px;">CSS3</a> <a href="/tags/Dart/" style="font-size: 14.44px;">Dart</a> <a href="/tags/Flutter/" style="font-size: 16.67px;">Flutter</a> <a href="/tags/Git/" style="font-size: 12.22px;">Git</a> <a href="/tags/HTML/" style="font-size: 14.44px;">HTML</a> <a href="/tags/HTML5/" style="font-size: 12.22px;">HTML5</a> <a href="/tags/JSON/" style="font-size: 10px;">JSON</a> <a href="/tags/Java/" style="font-size: 11.11px;">Java</a> <a href="/tags/JavaScript/" style="font-size: 20px;">JavaScript</a> <a href="/tags/Javascript/" style="font-size: 10px;">Javascript</a> <a href="/tags/QT/" style="font-size: 12.22px;">QT</a> <a href="/tags/React/" style="font-size: 15.56px;">React</a> <a href="/tags/Sass/" style="font-size: 11.11px;">Sass</a> <a href="/tags/TheKnowledgeOf/" style="font-size: 11.11px;">TheKnowledgeOf</a> <a href="/tags/TypeScript/" style="font-size: 10px;">TypeScript</a> <a href="/tags/bootstrap/" style="font-size: 11.11px;">bootstrap</a> <a href="/tags/jQuery/" style="font-size: 13.33px;">jQuery</a>
    </div>
  </div>

  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Archives</h3>
    <div class="widget">
      <ul class="archive-list"><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/12/">December 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/11/">November 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/10/">October 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/09/">September 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/08/">August 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/07/">July 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/06/">June 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/05/">May 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/04/">April 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/03/">March 2019</a></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Recent Posts</h3>
    <div class="widget">
      <ul>
        
          <li>
            <a href="/2019/12/29/Flutter-MaterialApp常用属性介绍/">Flutter-MaterialApp常用属性介绍</a>
          </li>
        
          <li>
            <a href="/2019/12/29/Flutter-ListView/">Flutter-ListView</a>
          </li>
        
          <li>
            <a href="/2019/12/29/Flutter-AppBar/">Flutter-AppBar</a>
          </li>
        
          <li>
            <a href="/2019/12/29/Flutter-TabBar/">Flutter-TabBar</a>
          </li>
        
          <li>
            <a href="/2019/12/29/Flutter-按钮/">Flutter-按钮</a>
          </li>
        
      </ul>
    </div>
  </div>

  
</aside>
        
      </div>
      <footer id="footer">
  
  <div class="outer">
    <div id="footer-info" class="inner">
      &copy; 2019 John Doe<br>
      Powered by <a href="http://hexo.io/" target="_blank">Hexo</a>
    </div>
  </div>
</footer>
    </div>
    <nav id="mobile-nav">
  
    <a href="/" class="mobile-nav-link">Home</a>
  
    <a href="/archives" class="mobile-nav-link">Archives</a>
  
</nav>
    

<script src="//ajax.googleapis.com/ajax/libs/jquery/2.0.3/jquery.min.js"></script>


  <link rel="stylesheet" href="/fancybox/jquery.fancybox.css">
  <script src="/fancybox/jquery.fancybox.pack.js"></script>


<script src="/js/script.js"></script>



  </div>
</body>
</html>